function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function quickSort(arr) {
  _quickSort(arr, 0, arr.length - 1)
  return arr
}

function _quickSort(arr, left, right) {
  if (left >= right) return
  let p = partition1(arr, left, right)
  _quickSort(arr, left, p - 1)
  _quickSort(p + 1, right)
}
// 写法一
function partition1(arr, begin, end) {
  // 每次以begin 作为为 基准
  let left = begin,
    right = end
  while (left < right) {
    while (left < right && arr[right] >= arr[begin]) right--
    while (left < right && arr[left] <= arr[begin]) left++
    swap(arr, left, right)
  }
  swap(arr, begin, left)
  return left
}

// 写法二
function partition2(arr, left, right) {
  let p = arr[left]
  let index = left // index 代表 左边的都比 p小或者等于   右边的都比p大
  for (let i = index + 1; i <= right; i++) {
    let num = arr[i]
    if (num < p) {
      swap(arr, index + 1, i)
      index++
    }
  }
  swap(arr, left, index)
  return index
}

;[, , , , , , , , ,]
